package com.fr.lintcode;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月9日
*时间：上午11:48:18
*/
public class Q131 {
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
        ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
        if (buildings == null || buildings.length <= 0) {
            return rs;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for (int[] a : buildings) {
            for (int i = a[0]; i < a[1]; i++) {
                Integer height = map.get(i);
                if (height == null || height < a[2]) {
                    map.put(i, a[2]);
                }
            }
            if (max < a[1]) {
                max = a[1];
            }
        }
        int first = 0;
        int end = 0;
        int nowH = -1;
        for (int i = 0; i <= max; i++) {
            Integer height = map.get(i);
            if (height != null && height > 0) {
                if (nowH > 0) {
                    if (nowH != height) {
                        ArrayList<Integer> result = new ArrayList<>();
                        result.add(first);
                        result.add(end);
                        result.add(nowH);
                        rs.add(result);
                        nowH = height;
                        first = i;
                        end = i + 1;
                    } else {
                        end = i + 1;
                    }
                } else {
                    first = i;
                    end = i + 1;
                    nowH = height;
                }
            } else if (nowH > 0) {
                ArrayList<Integer> result = new ArrayList<>();
                result.add(first);
                result.add(end);
                result.add(nowH);
                rs.add(result);
                nowH = -1;
                first = i;
            }
        }
        if (nowH > 0) {
            ArrayList<Integer> result = new ArrayList<>();
            result.add(first);
            result.add(max);
            result.add(nowH);
            rs.add(result);
        }
        return rs;
    }

    @Test
    public void testA() throws IOException {
        // int[][] buildings = { { 1, 3, 3 }, { 2, 4, 4 }, { 5, 6, 1 } };
        // int[][] buildings = { { 1, 10, 3 }, { 2, 5, 8 }, { 7, 9, 8 } };
        File f = new File("C:\\Users\\Hunteron\\Downloads\\15.in");
        FileReader fr = new FileReader(f);
        @SuppressWarnings("resource")
        BufferedReader br = new BufferedReader(fr);
        String line = br.readLine();
        String[] s = line.split("},");
        int[][] buildings = new int[s.length][3];
        for (int i = 0; i < s.length; i++) {
            String n[] = s[i].split(",");
            if (n.length == 3) {
                buildings[i][0] = Integer.parseInt(n[0]);
                buildings[i][1] = Integer.parseInt(n[1]);
                buildings[i][2] = Integer.parseInt(n[2]);
            }
        }
        long begin = System.currentTimeMillis();
        ArrayList<ArrayList<Integer>> rs = buildingOutline(buildings);
        System.out.println(System.currentTimeMillis() - begin);
        System.out.println(rs);
    }
}
